#pragma once
#include "stdafx.h"

typedef adjacency_list<vecS, vecS, undirectedS, 
property<vertex_name_t, string>> Graph;
typedef graph_traits<Graph>::vertices_size_type Index;
typedef hash_set<Index> Indset;
typedef graph_traits<Graph>::vertex_iterator VIter;
typedef graph_traits<Graph>::adjacency_iterator AdjItr;

class Clique
{
public:
	Clique(const Graph& g);
	void findIndependentSet(Graph& g);
private:
	Clique();
	Indset Q, maxQ;
	size_t maxS;
	const Graph& G;
	void mainExpand();
	void expand(const Indset& subg, Indset& cand);
	//return set of neighbourhood verteces of vertex from subg
	//which has maximal intersection between 
	//its neighbourhood and cand set
	void neighbourhood(const Indset& subg, const Indset& cand, Indset& result);
	//return intersection of a, b sets
	template <typename Set, typename AdjIter>
	void intersection(pair<AdjIter,AdjIter> adj, const Set& a, Set& b);
	//return a-b
	template <typename Set>
	void difference(Set& a, const Set& b);
};